#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50001;
long long  dp[2][maxn];
int N,K,l,r,q[maxn];

struct node
{
	long long w,h;
	bool friend operator <(node a,node b)
	{
		if(a.w==b.w)
			return a.h>b.h;
		return a.w<b.w;
	}
}a[maxn];

long long  min(long long x,long long y)
{
	return x<y?x:y;
}
long long Abs(long long x)
{
	return x<0?-x:x;
}
bool check1(int i,int j1,int j2,int sl)
{
	long long Y=dp[(i-1)&1][j1]-dp[(i-1)&1][j2];
	Y=Abs(Y);
	long long X=a[j1+1].h-a[j2+1].h;
	X=Abs(X);
	if(Y<=X*sl)return true;
	return false;
}

bool check2(int i,int j1,int j2,int j3)
{
	long long y1=dp[(i-1)&1][j1]-dp[(i-1)&1][j2];
	long long x1=a[j2+1].h-a[j1+1].h;
	long long y2=dp[(i-1)&1][j2]-dp[(i-1)&1][j3];
	long long x2=a[j3+1].h-a[j2+1].h;
	if(y1*x2>y2*x1)return true;
	return false;
}
int main()
{
	while(scanf("%d%d",&N,&K)!=EOF)
	{
		memset(q,0,sizeof(q));
		for(int i=1;i<=N;i++)
			scanf("%lld%lld",&a[i].w,&a[i].h);
		sort(a+1,a+N+1);
		l=r=1;q[1]=1;
		for(int i=2;i<=N;i++)
		{
			if(a[i].w==a[q[r]].w)continue;
			while(l<=r&&a[i].h>=a[q[r]].h)r--;
			r++;q[r]=i;
		}
		for(int i=1;i<=r;i++)
		{
			a[i].w=a[q[i]].w;
			a[i].h=a[q[i]].h;
		}
		N=r;if(K>N)K=N;
		for(int i=1;i<=N;i++)dp[1][i]=a[1].h*a[i].w;
		long long ans=dp[1][N];
		for(int i=2;i<=K;i++)
		{
			l=r=1;q[1]=i-1;
			for(int j=i;j<=N;j++)
			{
				while(l<r&&check1(i,q[l],q[l+1],a[j].w))l++;
				dp[i&1][j]=dp[(i-1)&1][q[l]]+a[q[l]+1].h*a[j].w;
				while(l<r&&check2(i,q[r-1],q[r],j))r--;
				r++;q[r]=j;
			}
			ans=min(ans,dp[i&1][N]);
		}
		cout<<ans<<endl;
	}
	return 0;
}
